package hot_100;

public class 实现Trie前缀树 {
    public static void main(String[] args) {

    }


    int[][] tr = new int[10010][26];
    int[] cnt = new int[10010];
    int idx = 0;

    public void insert(String word) {
        char[] ch = word.toCharArray();
        int p = 0;
        for (char c : ch) {
            int s = c - 'a';
            if (tr[p][s] == 0) {
                tr[p][s] = ++idx;
            }
            p = tr[p][s];
        }
        cnt[p]++;
    }

    public boolean search(String word) {
        char[] ch = word.toCharArray();
        int p = 0;
        for (char c : ch) {
            int s = c - 'a';
            if (tr[p][s] == 0) {
                return false;
            }
            p = tr[p][s];
        }
        return cnt[p] != 0;
    }

    public boolean startsWith(String prefix) {
        char[] ch = prefix.toCharArray();
        int p = 0;
        for (char c : ch) {
            int s = c - 'a';
            if (tr[p][s] == 0) {
                return false;
            }
            p = tr[p][s];
        }
        return true;
    }
}
